/**
 * @file 有一个迷宫，有很多障碍没法走，1表示，丸子的位置在某一个点(2)，公主在某一个点(3)，求丸子救出公主，最少需要多少步，并把路线输出出来
 * @author
 */

const getMaze = () => {
    return [
        [2, 0, 1, 0, 0, 0, 0],
        [0, 0, 1, 0, 0, 1, 0],
        [0, 1, 1, 0, 0, 1, 0],
        [0, 1, 0, 1, 0, 1, 0],
        [0, 0, 0, 0, 0, 1, 0],
        [0, 1, 1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1, 3, 0]
    ];
};

const createPoint = ({x, y, stepCount, prevPoint}) => {
    return {x, y, stepCount, prevPoint};
};

// 队列
// const bfs = () => {
//     创建一个队列，1个初始的点
//     while (判断队列是否为空) {
//         从队头弹出一个当前层要处理的节点
// 
//         for (以此节点找出所有可以触达的节点) {
//             if (judge) {
//                 创建新的节点
//                 新的节点的某些值(count)要在上一个节点的基础上 + 1
//                 新的节点进入队列
//                 if (碰到了你应该终结的节点) {
//                     结束，输出你的某些值（count）
//                     return;
//                 }
//             }
//         }
//     }
// };

const judge = (maze, {x, y}) => {
    return (x >= 0) && (y >= 0)
        && (x < maze.length) && (y < maze[0].length)
        && (maze[x][y] !== 1);
};

const run = (maze, maru) => {

    const maruPoint = createPoint({
            stepCount: 0,
            ...maru
        });
    let stepQueue = [maruPoint];

    const steps = [
        [1, 0],
        [0, 1],
        [-1, 0],
        [0, -1]
    ];

    while (stepQueue.length) {
        const curPoint = stepQueue.shift();
        maze[curPoint.x][curPoint.y] = 1;
        for (let i in steps) {
            const [vectorX, vectorY] = steps[i];
            const newX = curPoint.x + vectorX;
            const newY = curPoint.y + vectorY;
            if (judge(maze, {x: newX, y: newY})) {

                const newPoint = createPoint({
                    x: newX,
                    y: newY,
                    stepCount: curPoint.stepCount + 1,
                    prevPoint: curPoint
                });

                if (maze[newPoint.x][newPoint.y] == 3) {
                    console.log(newPoint.stepCount);
                    let runPoint = newPoint;
                    while (runPoint) {
                        console.log('整体倒着的路径是：', runPoint.x, runPoint.y);
                        runPoint = runPoint.prevPoint;
                    }
                    console.log('找到公主了！');
                }

                maze[newPoint.x][newPoint.y] = 1;
                // console.log('maz:::', maze);
                stepQueue.push(newPoint);
            }
        }
    }
};

const start = () => {
    let maze = getMaze();
    run(maze, {
        x: 0,
        y: 0
    });
};

start();
